#include <stdio.h>
#include <math.h>
#include <stdlib.h>
#include <stdbool.h>

//https://leetcode.cn/problems/insertion-sort-list/submissions/

struct ListNode {
    int val;
    struct ListNode *next;
};


struct ListNode* insertionSortList(struct ListNode* head){
    if (head == NULL || head->next == NULL) {
        return head;
    }
    struct ListNode *preHead = (struct ListNode *) malloc((sizeof(struct ListNode)));
    preHead->next = head;
    struct ListNode *prev = head;
    struct ListNode *curr = head->next;
    while (curr) {                                  // 只遍历一遍
        if (curr->val < prev->val) {                // 前 > 后
            struct ListNode *pstr = preHead;        // 创建一个
            while (pstr->next->val < curr->val) {   // 找到: 前 < 插 < 后
                pstr = pstr->next;
                curr = prev->next;
            }
            prev->next = curr->next;                // 交换
            curr->next = pstr->next;                // 画图
            pstr->next = curr;
            curr = prev->next;
        } else {                                    // 后移
            prev = curr;
            curr = prev->next;
        }
    }
    return preHead->next;
}


int main() {

    return 0;
}